Modern circuits typically are designed using some form of computer aided design (CAD) tool. Using a CAD tool, a software representation of a circuit design can be generated. This software representation, often referred to as a netlist, specifies the logic and logical connectivity, i.e. nets, of the circuit design. Software-based place and route tools are responsible for assigning, or placing, instances of the various circuit structures to physical locations on an integrated circuit (IC). Routing refers to the process of determining physical implementations of the nets that achieve the specified logical connectivity.
Traditional routing techniques have routed multi-fanout nets one load at a time. A multi-fanout net is a net that has more than one load. Modern ICs include very large multi-fanout nets, having many loads. In the conventional approach, each load of a multi-fanout net is routed independently of the others, one after the other sequentially. A minimum cost solution is found for each load. Each routing solution for a given source-load signal path is provided by a routing expansion. In using this approach, the number of routing expansions required to route a single multi-fanout net generally is proportional to the number of loads of the multi-fanout net.
Typically, a breadth-first search algorithm is used to process an underlying graph representation of the circuit design to determine a routing for each source-load signal path of a multi-fanout net. The graph representation can be that of a grid which represents the routing fabric of a device. Within the grid model, the entire routing surface is represented as a rectangular array of cells or nodes.
Routing each load of a multi-fanout net individually does have disadvantages. One such disadvantage is that a significant amount of run-time is needed to route a multi-fanout net. In general, the runtime required to route a multi-fanout net increases with the complexity of the net topology. Accordingly, as circuit designs and ICs become more complex, the time required to route the devices, particularly with respect to multi-fanout nets, also increases.
Another disadvantage is that the quality of a route for a given multi-fanout net often varies according to the order in which the loads of the multi-fanout net are routed. As each load is routed, the routing resources that are available for routing as yet unrouted loads of the multi-fanout net are decreased. Decreasing the pool of available routing resources means that fewer routing solutions can be determined from the pool. With respect to an overall circuit design, routing each load of a given multi-fanout net individually can produce a situation in which the resulting route is locally optimal, but not globally optimal.
Further, because the order in which loads of a multi-fanout net is routed can vary, routing symmetry is not maintained. This means that the routes for the different signal paths of a multi-fanout net can vary significantly with respect to one another. As a result, each signal path may have a very different signal propagation delay, thereby causing delay skew issues in the circuit design.
So called single expansion routers address some of the limitations of conventional routers, particularly in relation to routing multi-fanout nets. A single expansion router can route each signal path of a multi-fanout net in a single routing expansion. Single expansion routers treat all loads of the multi-fanout net as a single problem. During a single routing expansion, the router begins with the source and locates as many loads as possible. Rather than terminating when a first load is located, the routing expansion continues until a programmable interconnection point (PIP) limit is reached or until all loads of the multi-fanout net have been found. An example of a single expansion router is described in VPR: A New Packing, Placement, and Routing Tool for FPGA Research, 1997 International Workshop on Field Programmable Logic and Applications, Vaughn Betz, et al. (1997).
By routing a multi-fanout net in a single expansion, the complexity of the route problem is no longer dependent upon the number of loads of the net. Instead, complexity is dependent upon the predetermined PIP limit that is set and the routing architecture of the IC. Accordingly, when routing a multi-fanout net that is geographically large, the PIP limit must be set to a value that is large enough to ensure that the router locates most, if not all, of the loads.
Single expansion routers, however, also have disadvantages. In particular, when large PIP limits are established, the run-time performance of single expansion routers tends to degrade rapidly. Though high PIP limits are needed when routing large nets, high PIP limits can lead to a situation in which the router visits most, if not all, routing resources of the IC during an expansion. For larger ICs, the run-time performance of a single expansion router generally becomes dependent upon the number of nodes in the IC. As such, the run-time performance of a single expansion router tends to scale poorly as the size of an IC increases.
It would be beneficial to limit the number of routing resources that are explored for routing a multi-fanout net, thereby decreasing the run-time of a router.